// #include<vector>
// using namespace std;
// class Solution {
// public:
//     int serach(vector<int>&mul,int l,int r,int target){
//         int d=mul[l-1];
//         while(l<r){
//             int mid=(l+r)>>1;
//             if(mul[mid]/d>=target)
//                 r=mid;
//             else
//                 l=mid+1;
//         }
//         return l;
//     }
//     int numSubarrayProductLessThanK(vector<int>& nums, int k) {
//         vector<int>mul(nums.size()+2);
//         mul[0]=1;
//         mul[1]=nums[0];
//         for(int i=2;i<mul.size()-1;i++){
//             mul[i]=nums[i-1];
//             mul[i]*=mul[i-1];
//         }
//         for(auto e:mul)
//             cout<<e<<' ';
//         int res=0;
//         cout<<endl;
//         for(int i=1;i<mul.size()-1;i++){
//             int p=serach(mul,i,mul.size()-1,k);
//             if(p!=i){
//                 res+=p-i;
//             cout<<p-i<<endl;
//             }
//         }
//         return res;
//     }
// };
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
class Solution
{
public:
    int numSubarrayProductLessThanK(vector<int> &nums, int k)
    {
        if (k == 0)
            return 0;
        vector<double> mul(nums.size() + 1);
        for (int i = 1; i < mul.size(); i++)
        {
            mul[i] = log(nums[i - 1]);
            mul[i] += mul[i - 1];
        }
        int res = 0;
        double target = log(k);
        for (int i = 1; i < nums.size(); i++)
        {
            int p = lower_bound(mul.begin(), mul.begin() + i + 1, mul[i + 1] - log(k) + 1e-10) - mul.begin();
            res += i + 1 - p;
        }
        return res ? res + 1 : res;
    }
};